package com.mrzhou.study.struct.array;

import lombok.SneakyThrows;

import javax.validation.constraints.NotNull;
import java.io.*;

/**
 * 稀疏数组:
 *  介绍及思路见: classpath: doc/Java数据结构和算法.pdf  ~ 3.1节
 */
public class ArraySparse {

    /**
     * 将 普通数组装换成一个稀疏数组
     */
    public static int[][] toSparseArray(@NotNull final int[][] origin) {
        /** 统计全部的非零整数的个数 */
        int sum = 0; //
        for(int i = 0; i < origin.length; i++) {
            for(int y = 0; y < origin[i].length; y++) {
                System.out.print(origin[i][y] + "\t");
                if(origin[i][y] > 0) {
                    sum ++;
                }
            }
            System.out.print("\n");
        }

        /** 创建稀疏数组, 保存原始数组中的数据 */
        int[][] sparse = new int[sum + 1][3]; // 稀疏数组的第一行保存原始数组全局信息(多少行, 多少列, 多少非初始数据)
        sparse[0][0] = origin.length; // 保存原始数据有多少行
        sparse[0][1] = origin[0].length; // 保存原始数组有多少列
        sparse[0][2] = sum; // 保存原始数组有多少非初始数据
        /** 再次遍历原始数组, 获取其中非初始数据的信息 */
        int count = 1; // 用于定义将非初始数据保存到稀疏数组中的位置, 因0行数据以保存原始二维数组的基本信息, 因此count初始值为1
        for(int i = 0; i < origin.length; i++) {
            for(int y = 0; y < origin[i].length; y++) {
                if(origin[i][y] > 0) { // 获取非原始数据
                    sparse[count][0] = i; // 保存非原始数据行的位置
                    sparse[count][1] = y; // 保存非原始数据列的位置
                    sparse[count][2] = origin[i][y]; // 保存非原始数据的值
                    count++;
                }
            }
        }

        /** 输出装换过后的稀疏数组 */
        System.out.printf("\n装换过后的稀疏数组为: \n");
        for(int i = 0; i < sparse.length; i++) {
            System.out.printf("%d\t%d\t%d\n", sparse[i][0], sparse[i][1], sparse[i][2]);
        }
        return sparse;
    }

    /**
     * 将稀疏数组转换成普通数组
     * @return
     */
    public static int[][] toNormalArray(@NotNull final int[][] origin) {
        // 取出稀疏数组的第一行数据, 初始化数组
        int[][] target = new int[origin[0][0]][origin[0][1]];
        for (int i = 1; i < origin.length; i++) {
            target[origin[i][0]][origin[i][1]] = origin[i][2];
        }
        return target;
    }

    /**
     * 将稀疏数组保存到本地磁盘
     * @param path
     * @param sparseArray
     * @throws IOException
     */
    public static void write(String path, int[][] sparseArray) throws IOException {
        ObjectOutputStream oos = new ObjectOutputStream(new FileOutputStream(path));
        oos.writeObject(sparseArray);
        oos.flush();
        oos.close();
    }

    @SneakyThrows
    public static int[][] read(String path) {
        ObjectInputStream ois = new ObjectInputStream(new FileInputStream(path));
        int[][]  sparse = (int[][])ois.readObject();
        return sparse;
    }

    public static void printArray(int[][] array) {
        for(int i = 0; i < array.length; i++) {
            for(int y = 0; y < array[i].length; y++) {
                System.out.print(array[i][y] + "\t");
            }
            System.out.print("\n");
        }
    }

    @SneakyThrows
    public static void main(String[] args) {
        int[][] origin = new int[15][15];
        origin[14][13] = 34;
        origin[12][3] = 45;
        origin[4][9] = 65;
        origin[8][6] = 99;
        System.out.println("\n============将稀疏数组转换成普通数组============");
        String path = "C:/Users/EDZ/Desktop/map.data";
        write(path, toSparseArray(origin));
        System.out.println("\n============从磁盘中读取稀疏数组============");
        printArray(toNormalArray(read(path)));
    }

}
